#-*-coding:utf-8-*-
#算法习题
# 1 两数之和
# 给定数组nums和target 找出和为target的两个数,并且返回下标
# method01 :两层for循环解决问题
# method2 :利用dict保存已经遍历过得数据
#from day03 import calRunTime


def getTwoNumber(arr,target):
	idx0,idx1 = -1,-1
	if not arr:
		return idx0,idx1
	totalCount = len(arr)
	for i in xrange(0,totalCount-1):
		for j in xrange(1,totalCount):
			if arr[i] + arr[j] == target:
				idx0 = i
				idx1 = j
				break

	return idx0,idx1


def hashMapGetTwoNumber(arr,target):
	tmpDict = {}
	for idx,num in enumerate(arr):
		secNum = target - num
		if tmpDict.has_key(secNum):
			return idx,tmpDict[secNum]
		else:
			tmpDict.update({num:idx})
	return (-1,-1)



# 2 无重复字符最长子串
# key:滑动窗口
def longestSubStr(strObj):
	left,right,maxWindowLength = 0,0,0
	totalCount = len(strObj)
	tmpList = []
	while((left<totalCount) and (right < totalCount)):
		curStr =  strObj[right]
		if curStr in tmpList:
			tmpList.remove(curStr)
			left += 1
		else:
			tmpList.append(curStr)
			right += 1
		curLength = right - left
		maxWindowLength = curLength if curLength >= maxWindowLength else maxWindowLength

	return maxWindowLength

# 3 最长回文子串
# key:中心扩散



# 4 x 的平方根
# key: 二分
def mySqrt(x):
	left,right,ret = 0,x,0
	while(left <= right):
		mid = left+(right-left)/2
		if (pow(mid,2) <= x):
			left = mid+1
			ret = mid
		else:
			right = mid-1
	return ret

#5 合并有序数据
# key:两个指针

# def mergeTwoList(listA,listB):
# 	left,right = 0,0
# 	m,n = len(listA),len(listB)
# 	newList = {}
# 	min = 0
# 	while(left < m or right < n):
# 		if left == m:
# 			n += 1
# 			min = listB[right]
# 		elif right == n:
# 			left += 1
# 			min = listA[left]
# 		elif listA[left] < listB[right]:
# 			min = listA[left]
# 			left += 1
# 		else:
# 			min = listB[right]
# 			right += 1
# 		newList[left+right-1] = min
#
# 	for idx in xrange(m+n):
# 		listA[idx] = newList[idx]
# 	return listA

if __name__ == "__main__":
	#print getTwoNumber([1,2,3,4,5],5)
	print longestSubStr("pwwkew")
	print longestSubStr("bbbbb")
	print mySqrt(9)
	#print mergeTwoList([1,2,5,8,9],[0,4,3,7,10])
	methods =  dir(object)
	print  methods